template<class T>
struct CartesianTree {
  CartesianTree(vector<T> &val) {
    ls.assign(val.size(), -1);
    rs.assign(val.size(), -1);

    vector<int> stk;
    for (int i = 0; i < (int)val.size(); i++) {
      int y = -1;
      while (!stk.empty() && val[stk.back()] > val[i]) {
        y = stk.back();
        stk.pop_back();
      }

      if (y != -1) {
        ls[i] = y;
      }
      if (!stk.empty()) {
        rs[stk.back()] = i;
      } else {
        rt = i;
      }
      stk.emplace_back(i);
    }
  }

  int rt;
  vector<int> ls, rs;
};